package 串;

public class KMP {

	public static void main(String[] args) {
		System.out.println(kmp("Hello World", "H") == 0);
		System.out.println(kmp("Hello World", "or") == 7);
		System.out.println(kmp("Hello World", "d") == 10);
	}

	public static int kmp(String text, String pattern) {
		if (text == null || pattern == null) return -1;
		int tlen = text.length(), plen = pattern.length();
		if (tlen == 0 || plen == 0 || plen > tlen) return -1;

		char[] tChars = text.toCharArray();
		char[] pChars = pattern.toCharArray();
		int[] next = next1(pChars);
		int ti = 0, pi = 0;
		int tiMax = tlen - plen;
		while (pi < plen && ti - pi <= tiMax) {
			if (pi < 0 || tChars[ti] == pChars[pi]) {
				pi++;
				ti++;
			} else {
				pi = next[pi];
			}
		}
		return pi == plen ? ti - pi : -1;
	}
	
	private static int[] next(char[] pattern) {
		int[] next = new int[pattern.length];
		int n = next[0] = -1;
		int i = 0;
		int iMax = next.length - 1;
		while (i < iMax) {
			if (n < 0 || pattern[i] == pattern[n]) {
				next[++i] = ++n;
			} else {
				n = next[n];
			}
		}
		return next;
	}
	
	/**
	 * 优化: i, n元素相同时, 若i + 1与n + 1元素也相同, 则i + 1失配时, n + 1也会失配
	 * 所以: next[i + 1] = next[n + 1];
	 */
	private static int[] next1(char[] pattern) {
		int[] next = new int[pattern.length];
		int n = next[0] = -1;
		int i = 0;
		int iMax = next.length - 1;
		while (i < iMax) {
			if (n < 0 || pattern[i] == pattern[n]) {
				i++;
				n++;
				if (pattern[i] == pattern[n]) {
					next[i] = next[n];
				} else {
					next[i] = n;
				}
			} else {
				n = next[n];
			}
		}
		return next;
	}
}
